/*
 * @Author: sjr
 * @Date: 2021-01-27 22:52:12
 * @LastEditTime: 2021-01-28 09:49:32
 * @LastEditors: sjr
 * @Description: 描述
 * @FilePath: \leetcode\109.有序链表转换二叉搜索树.js
 */
/*
 * @lc app=leetcode.cn id=109 lang=javascript
 *
 * [109] 有序链表转换二叉搜索树
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {ListNode} head
 * @return {TreeNode}
 */
var sortedListToBST = function(head) {
  if(!head) return null
  if(!head.next) return new TreeNode(head.val)
  let slow = head
  let fast = head
  let pre = null
  while(fast&&fast.next){
    pre = slow
    slow = slow.next
    fast = fast.next.next
  }
  pre.next = null

  let root = new TreeNode(slow.val)
  root.left = sortedListToBST(head)
  root.right = sortedListToBST(slow.next)

  return root
};
// @lc code=end

